<!DOCTYPE html>



  


<html class="theme-next gemini use-motion" lang="zh-Hans">
<head><meta name="generator" content="Hexo 3.9.0">
  <meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
<meta name="theme-color" content="#222">









<meta http-equiv="Cache-Control" content="no-transform">
<meta http-equiv="Cache-Control" content="no-siteapp">
















  
  
  <link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css">




  
  
  
  

  
    
    
  

  

  

  
    
      
    

    
  

  
    
      
    

    
  

  
    
    
    <link href="//fonts.googleapis.com/css?family=Lato:300,300italic,400,400italic,700,700italic|Lobster Two:300,300italic,400,400italic,700,700italic|Roboto Mono:300,300italic,400,400italic,700,700italic&subset=latin,latin-ext" rel="stylesheet" type="text/css">
  






<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css">

<link href="/css/main.css?v=5.1.4" rel="stylesheet" type="text/css">


  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png?v=5.1.4">


  <link rel="mask-icon" href="/images/logo.svg?v=5.1.4" color="#222">





  <meta name="keywords" content="操作系统,linux,进程调度,">










<meta name="description" content="操作系统导论（进程篇）前言操作系统作为计算机基础学科之一，其经过多年的发展，内容多而全，知识几乎横跨平时编程中接触的所有概念。重新温习操作系统，一是可以让我们对开发有一个底层的认知，遇到问题可以多一条思路；二是扩大知识面和加深理解，现代很多技术的实现中都能看到操作系统的概念，和相关解决方案。 大部分同学在首次接触学习操作系统的过程中，会遇到很多阻力，究其原因一是因为操作系统需要很多前置知识才能理解">
<meta name="keywords" content="操作系统,linux,进程调度">
<meta property="og:type" content="article">
<meta property="og:title" content="操作系统导论(进程篇)">
<meta property="og:url" content="https://yujunjiex.gitee.io/2021/03/17/操作系统导论-进程篇/index.html">
<meta property="og:site_name" content="Yu&#39;s Home">
<meta property="og:description" content="操作系统导论（进程篇）前言操作系统作为计算机基础学科之一，其经过多年的发展，内容多而全，知识几乎横跨平时编程中接触的所有概念。重新温习操作系统，一是可以让我们对开发有一个底层的认知，遇到问题可以多一条思路；二是扩大知识面和加深理解，现代很多技术的实现中都能看到操作系统的概念，和相关解决方案。 大部分同学在首次接触学习操作系统的过程中，会遇到很多阻力，究其原因一是因为操作系统需要很多前置知识才能理解">
<meta property="og:locale" content="zh-Hans">
<meta property="og:image" content="https://yujunjiex.gitee.io/2021/03/17/操作系统导论-进程篇/3059ccfe06aeb567c2a97322ee4a390f.jpeg">
<meta property="og:image" content="https://yujunjiex.gitee.io/2021/03/17/操作系统导论-进程篇/C0C31C2A-4834-46C2-9D8A-772E98C44E54.png">
<meta property="og:image" content="https://yujunjiex.gitee.io/2021/03/17/操作系统导论-进程篇/6665E428-AEC0-4A84-95FA-28B7E90A0BB4.png">
<meta property="og:image" content="https://yujunjiex.gitee.io/2021/03/17/操作系统导论-进程篇/D9FF427C-DC64-4ED0-A929-8DB4D609957F.jpg">
<meta property="og:image" content="https://yujunjiex.gitee.io/2021/03/17/操作系统导论-进程篇/971D1520-2FAA-458B-B02A-05359281A29C.jpg">
<meta property="og:image" content="https://yujunjiex.gitee.io/2021/03/17/操作系统导论-进程篇/3EDEB3BC-C8D4-4FD0-A82A-BEED1C87D264.png">
<meta property="og:image" content="https://yujunjiex.gitee.io/2021/03/17/操作系统导论-进程篇/739D47E6-4A1E-44D8-9536-E3D149F9211C.png">
<meta property="og:image" content="https://yujunjiex.gitee.io/2021/03/17/操作系统导论-进程篇/11E32EB5-6CC6-4F70-A361-9C2C6A304A59.png">
<meta property="og:image" content="https://yujunjiex.gitee.io/2021/03/17/操作系统导论-进程篇/09E5948F-7E98-4896-B426-CB1DDDDABB14.png">
<meta property="og:image" content="https://yujunjiex.gitee.io/2021/03/17/操作系统导论-进程篇/F70CB601-035D-4DA4-83ED-C7817ED1241C.png">
<meta property="og:image" content="https://yujunjiex.gitee.io/2021/03/17/操作系统导论-进程篇/CF57A32E-5637-4BCC-B3B1-EDFE74F41464.png">
<meta property="og:image" content="https://yujunjiex.gitee.io/2021/03/17/操作系统导论-进程篇/08210689-F1C3-47A6-8D20-2F4FD40C93B2.png">
<meta property="og:image" content="https://yujunjiex.gitee.io/2021/03/17/操作系统导论-进程篇/E084EA4F-08FE-40A7-98C3-8B2434988445.png">
<meta property="og:image" content="https://yujunjiex.gitee.io/2021/03/17/操作系统导论-进程篇/E1D5FAC7-B358-478D-AC0B-DB4442B9EDBE.png">
<meta property="og:image" content="https://yujunjiex.gitee.io/2021/03/17/操作系统导论-进程篇/51EB5FB1-1E66-4B81-9FAE-A26B3219E8CD.png">
<meta property="og:image" content="https://yujunjiex.gitee.io/2021/03/17/操作系统导论-进程篇/9A51328E-8F57-43BA-8630-C1F01C642517.png">
<meta property="og:image" content="https://yujunjiex.gitee.io/2021/03/17/操作系统导论-进程篇/F757B999-B144-4A7D-9366-E6CF8E09CECC.png">
<meta property="og:image" content="https://yujunjiex.gitee.io/2021/03/17/操作系统导论-进程篇/D183F4D3-8393-49F3-85AC-ACA099EB5A9C.png">
<meta property="og:image" content="https://yujunjiex.gitee.io/2021/03/17/操作系统导论-进程篇/E442FEA5-57A6-4661-86CC-56CC93FD1643.png">
<meta property="og:image" content="https://yujunjiex.gitee.io/2021/03/17/操作系统导论-进程篇/4B39B5A0-65BB-471C-AC26-E766EB60D230.png">
<meta property="og:image" content="https://yujunjiex.gitee.io/2021/03/17/操作系统导论-进程篇/729EDA6F-CFDC-4EAD-9F05-C49A74EB05CA.png">
<meta property="og:image" content="https://yujunjiex.gitee.io/2021/03/17/操作系统导论-进程篇/1F679B26-15C8-4760-9AB1-259AB2BEEAAE.png">
<meta property="og:updated_time" content="2023-02-23T12:31:14.873Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="操作系统导论(进程篇)">
<meta name="twitter:description" content="操作系统导论（进程篇）前言操作系统作为计算机基础学科之一，其经过多年的发展，内容多而全，知识几乎横跨平时编程中接触的所有概念。重新温习操作系统，一是可以让我们对开发有一个底层的认知，遇到问题可以多一条思路；二是扩大知识面和加深理解，现代很多技术的实现中都能看到操作系统的概念，和相关解决方案。 大部分同学在首次接触学习操作系统的过程中，会遇到很多阻力，究其原因一是因为操作系统需要很多前置知识才能理解">
<meta name="twitter:image" content="https://yujunjiex.gitee.io/2021/03/17/操作系统导论-进程篇/3059ccfe06aeb567c2a97322ee4a390f.jpeg">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Gemini',
    version: '5.1.4',
    sidebar: {"position":"left","display":"hide","offset":12,"b2t":false,"scrollpercent":false,"onmobile":false},
    fancybox: true,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    duoshuo: {
      userId: '0',
      author: '博主'
    },
    algolia: {
      applicationID: '9PFXHHRD2G',
      apiKey: '45293228d8a5cecc1c0826fb3d34a130',
      indexName: 'blog',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"没有找到任何结果: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="https://yujunjiex.gitee.io/2021/03/17/操作系统导论-进程篇/">





  <title>操作系统导论(进程篇) | Yu's Home</title>
  





  <script type="text/javascript">
    var _hmt = _hmt || [];
    (function() {
      var hm = document.createElement("script");
      hm.src = "https://hm.baidu.com/hm.js?1746d8de4fb78edd21f9004d348fa6be";
      var s = document.getElementsByTagName("script")[0];
      s.parentNode.insertBefore(hm, s);
    })();
  </script>




</head>

<body itemscope="" itemtype="http://schema.org/WebPage" lang="zh-Hans">

  
  
    
  

  <div class="container sidebar-position-left page-post-detail">
    <div class="headband"></div>

    <header id="header" class="header" itemscope="" itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/" class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">Yu's Home</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <h1 class="site-subtitle" itemprop="description">管它真理无穷</h1>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br>
            
            首页
          </a>
        </li>
      
        
        <li class="menu-item menu-item-about">
          <a href="/about/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-user"></i> <br>
            
            关于Yu
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/tags/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-tags"></i> <br>
            
            标签
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/categories/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-th"></i> <br>
            
            分类
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br>
            
            归档
          </a>
        </li>
      

      
        <li class="menu-item menu-item-search">
          
            <a href="javascript:;" class="popup-trigger">
          
            
              <i class="menu-item-icon fa fa-search fa-fw"></i> <br>
            
            搜索
          </a>
        </li>
      
    </ul>
  

  
    <div class="site-search">
      
  <div class="popup search-popup local-search-popup">
  <div class="local-search-header clearfix">
    <span class="search-icon">
      <i class="fa fa-search"></i>
    </span>
    <span class="popup-btn-close">
      <i class="fa fa-times-circle"></i>
    </span>
    <div class="local-search-input-wrapper">
      <input autocomplete="off" placeholder="搜索..." spellcheck="false" type="text" id="local-search-input">
    </div>
  </div>
  <div id="local-search-result"></div>
</div>



    </div>
  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  

  
  
  

  <article class="post post-type-normal" itemscope="" itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="https://yujunjiex.gitee.io/2021/03/17/操作系统导论-进程篇/">

    <span hidden itemprop="author" itemscope="" itemtype="http://schema.org/Person">
      <meta itemprop="name" content="Yu">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/images/xiaomai.png">
    </span>

    <span hidden itemprop="publisher" itemscope="" itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Yu's Home">
    </span>

    
      <header class="post-header">

        
        
          <h2 class="post-title" itemprop="name headline">操作系统导论(进程篇)</h2>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2021-03-17T20:05:20+08:00">
                2021-03-17
              </time>
            

            

            
          </span>

          

          
            
              <span class="post-comments-count">
              <span class="post-meta-divider">|</span>
              <span class="post-meta-item-icon">
              <i class="fa fa-comment-o"></i>
              </span>
              <a href="/2021/03/17/操作系统导论-进程篇/#comments" itemprop="discussionUrl">
              <span class="post-comments-count valine-comment-count" data-xid="/2021/03/17/操作系统导论-进程篇/" itemprop="commentCount"></span>
              </a>
              </span>
            
          

          
          

          

          
            <div class="post-wordcount">
              
                
                <span class="post-meta-item-icon">
                  <i class="fa fa-file-word-o"></i>
                </span>
                
                  <span class="post-meta-item-text">字数统计&#58;</span>
                
                <span title="字数统计">
                  5,235
                </span>
              

              

              
            </div>
          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        <h1 id="操作系统导论（进程篇）"><a href="#操作系统导论（进程篇）" class="headerlink" title="操作系统导论（进程篇）"></a>操作系统导论（进程篇）</h1><h2 id="前言"><a href="#前言" class="headerlink" title="前言"></a>前言</h2><p>操作系统作为计算机基础学科之一，其经过多年的发展，内容多而全，知识几乎横跨平时编程中接触的所有概念。重新温习操作系统，一是可以让我们对开发有一个底层的认知，遇到问题可以多一条思路；二是扩大知识面和加深理解，现代很多技术的实现中都能看到操作系统的概念，和相关解决方案。</p>
<p>大部分同学在首次接触学习操作系统的过程中，会遇到很多阻力，究其原因一是因为操作系统需要很多前置知识才能理解，例如硬件设备，编译原理，汇编等等；二是因为操作系统中的概念太多且描述的很深奥，大部分场景没有实际经验是很难理解其真正含义。所以在上层开发积累了一定经验之后，接触到的很多概念，例如缓存，并发，持久化等等是可以回过头来套在操作系统底层知识一起理解的。</p>
<p>建议大家在工作之余，能够回头再来看看网络，操作系统一类的基础书籍，共同学习，会有很大的收获~</p>
<img src="/2021/03/17/操作系统导论-进程篇/3059ccfe06aeb567c2a97322ee4a390f.jpeg" alt="3059ccfe06aeb567c2a97322ee4a390f" style="zoom:75%;">

<a id="more"></a>

<h2 id="入口"><a href="#入口" class="headerlink" title="入口"></a>入口</h2><blockquote>
<p>refer: linux 0.11(操作系统在汇编初始化寄存器和扇区之后的入口逻辑)</p>
</blockquote>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">main</span><span class="params">(<span class="keyword">void</span>)</span> </span>&#123;</span><br><span class="line">    ROOT_DEV = ORIG_ROOT_DEV;</span><br><span class="line">    drive_info = DRIVE_INFO;</span><br><span class="line">    memory_end = (<span class="number">1</span>&lt;&lt;<span class="number">20</span>) + (EXT_MEM_K&lt;&lt;<span class="number">10</span>);</span><br><span class="line">    memory_end &amp;= <span class="number">0xfffff000</span>;</span><br><span class="line">    <span class="keyword">if</span> (memory_end &gt; <span class="number">16</span>*<span class="number">1024</span>*<span class="number">1024</span>)</span><br><span class="line">        memory_end = <span class="number">16</span>*<span class="number">1024</span>*<span class="number">1024</span>;</span><br><span class="line">    <span class="keyword">if</span> (memory_end &gt; <span class="number">12</span>*<span class="number">1024</span>*<span class="number">1024</span>) </span><br><span class="line">        buffer_memory_end = <span class="number">4</span>*<span class="number">1024</span>*<span class="number">1024</span>;</span><br><span class="line">    <span class="keyword">else</span> <span class="keyword">if</span> (memory_end &gt; <span class="number">6</span>*<span class="number">1024</span>*<span class="number">1024</span>)</span><br><span class="line">        buffer_memory_end = <span class="number">2</span>*<span class="number">1024</span>*<span class="number">1024</span>;</span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">        buffer_memory_end = <span class="number">1</span>*<span class="number">1024</span>*<span class="number">1024</span>;</span><br><span class="line">    main_memory_start = buffer_memory_end;</span><br><span class="line"></span><br><span class="line">    mem_init(main_memory_start,memory_end);</span><br><span class="line">    trap_init();</span><br><span class="line">    blk_dev_init();</span><br><span class="line">    chr_dev_init();</span><br><span class="line">    tty_init();</span><br><span class="line">    time_init();</span><br><span class="line">    sched_init();</span><br><span class="line">    buffer_init(buffer_memory_end);</span><br><span class="line">    hd_init();</span><br><span class="line">    floppy_init();</span><br><span class="line"></span><br><span class="line">    sti();</span><br><span class="line">    move_to_user_mode();</span><br><span class="line">    <span class="keyword">if</span> (!fork()) &#123;</span><br><span class="line">        init();</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">for</span>(;;) pause();</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>操作系统从概念上也是个软件程序。从上面入口可以看出操作系统做了各种初始化工作，包括内存初始化 mem_init, 中端初始化 trap_init, 时钟初始化 time_init, 进程调度初始化 sched_init 等等，学习操作系统时其实也是按这些模块进行划分。</p>
<p>并且可以发现操作系统的启动最后是一个死循环，用pause()怠速运行，那么操作系统是如何进行各种管理调度的呢？其实是通过中断，简单理解就是调用事先初始化好的各种函数~</p>
<h2 id="CPU虚拟化"><a href="#CPU虚拟化" class="headerlink" title="CPU虚拟化"></a>CPU虚拟化</h2><p>操作系统作为直接接触硬件的一层，如何将硬件抽象给现代使用场景是其最主要的职责。</p>
<p>人们在使用计算机的过程中，通常会同时运行浏览器，游戏，音乐播放器等等，如果机器只有一个CPU，操作系统是如何提供看起来有许多个CPU在同时进行工作的呢？</p>
<p>操作系统通过虚拟化 CPU 来提供这种假象。通过让一个进程只运行一个时间片，然后切换到其他进程执行，看似有很多个进程同时执行，实则并发，这就是时分复用(time sharing)。潜在的开销是性能损失，因为CPU共享，每个进程就会慢一些，并且还有上下文切换的成本。</p>
<h2 id="进程"><a href="#进程" class="headerlink" title="进程"></a>进程</h2><h3 id="进程API"><a href="#进程API" class="headerlink" title="进程API"></a>进程API</h3><p>● 创建（create）：操作系统必须包含一些创建新进程的方法。在shell中键入命令或双击应用程序图标时，会调用操作系统来创建新进程，运行指定的程序。</p>
<img src="/2021/03/17/操作系统导论-进程篇/C0C31C2A-4834-46C2-9D8A-772E98C44E54.png" alt="C0C31C2A-4834-46C2-9D8A-772E98C44E54" style="zoom:50%;">

<blockquote>
<p>进程的创建这里还有一些内存优化，写时复制和按需置零（等内存篇再讲）</p>
</blockquote>
<p>● 销毁（destroy）：由于存在创建进程的接口，因此系统还提供了一个强制销毁进程的接口。当然，很多进程会在运行完成后自行退出。但是，如果它们不退出，用户可能希望终止它们，因此停止失控进程的接口非常有用。</p>
<p>● 等待（wait）：有时等待进程停止运行是有用的，因此经常提供某种等待接口。</p>
<p>● 暂停和恢复：操作系统可以使进程暂停，然后恢复执行</p>
<p>● 状态（status）：通常也有一些接口可以获得有关进程的状态信息，例如运行了多长时间，或者处于什么状态。</p>
<h4 id="系统调用"><a href="#系统调用" class="headerlink" title="系统调用"></a>系统调用</h4><ul>
<li><p>fork()<br>用于从当前进程中创建一个新的子进程。与父进程的地址空间指向一模一样，通过返回值来区分是父进程和子进程</p>
</li>
<li><p>exec()<br>这个系统调用可以让子进程执行与父进程不同的程序。覆写进程的代码段，静态数据，堆，栈及其他内存空间，相当于直接替换为了另一个进程空间。</p>
</li>
<li><p>wait()<br>当父进程需要等待子进程执行完毕</p>
</li>
</ul>
<p><strong>fork+exec+wait的组合</strong></p>
<p>这些命令的分离和组合可以实现很多有用的功能，以一个shell调用为例：</p>
<blockquote>
<p>wc p3.c &gt; newfile.txt</p>
</blockquote>
<p>shell实现结果重定向的方式也很简单，当完成子进程的创建后，shell在调用exec()之前先关闭了标准输出（standardoutput），打开了文件newfile.txt。这样，即将运行的程序wc的输出结果就被发送到该文件，而不是打印在屏幕上。</p>
<p>现如今高级语言的subprocess一类的实现其实也是fork＋exec＋wait的组合。fork用于从当前进程中切出子进程，和父进程共享进程空间（写时复制前）并从当前/父进程的指令继续执行。exec用于在子进程中执行另外的程序，与父进程脱离开来，exec会将当前进程的用新的代码段覆写，重新初始化新的内存空间，并没有创建新的进程。wait用于等待子进程执行完成。</p>
<h3 id="进程状态机"><a href="#进程状态机" class="headerlink" title="进程状态机"></a>进程状态机</h3><p>● 运行（running）：在运行状态下，进程正在处理器上运行。这意味着它正在执行指令。</p>
<p>● 就绪（ready）：在就绪状态下，进程已准备好运行，但由于某种原因，操作系统选择不在此时运行。</p>
<p>● 阻塞（blocked）：在阻塞状态下，一个进程执行了某种操作，直到发生其他事件时才会准备运行。一个常见的例子是，当进程向磁盘发起I/O请求时，它会被阻塞，因此其他进程可以使用处理器。</p>
<p>● 初始（initial）：表示进程在创建时处于的状态</p>
<p>● 僵死（zombie）：表示进程已经退出但尚未清理的最终状态。如果父进程创建子进程后不调用 wait/waitpid，那内核保留的子进程信息不会被释放，进程号一直被占用。可以通过杀死父进程让僵尸子进程被init一号进程接管，它会自动释放系统进程表中的资源</p>
<img src="/2021/03/17/操作系统导论-进程篇/6665E428-AEC0-4A84-95FA-28B7E90A0BB4.png" alt="6665E428-AEC0-4A84-95FA-28B7E90A0BB4" style="zoom:75%;">

<blockquote>
<p>refer: 孤儿进程和僵死进程<a href="https://www.cnblogs.com/anker/p/3271773.html" target="_blank" rel="noopener">https://www.cnblogs.com/anker/p/3271773.html</a></p>
</blockquote>
<h3 id="进程数据结构"><a href="#进程数据结构" class="headerlink" title="进程数据结构"></a>进程数据结构</h3><p>操作系统为了跟踪每个进程的状态，会为所有的进程记录数据结构来保存关键信息，</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// the registers xv6 will save and restore</span></span><br><span class="line"><span class="comment">// to stop and subsequently restart a process</span></span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">context</span> &#123;</span></span><br><span class="line">  <span class="keyword">int</span> eip;</span><br><span class="line">  <span class="keyword">int</span> esp;</span><br><span class="line">  <span class="keyword">int</span> ebx;</span><br><span class="line">  <span class="keyword">int</span> ecx;</span><br><span class="line">  <span class="keyword">int</span> edx;</span><br><span class="line">  <span class="keyword">int</span> esi;</span><br><span class="line">  <span class="keyword">int</span> edi;</span><br><span class="line">  <span class="keyword">int</span> ebp;</span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line"><span class="comment">// the different states a process can be in</span></span><br><span class="line"><span class="keyword">enum</span> proc_state &#123; UNUSED, EMBRYO, SLEEPING,</span><br><span class="line">                  RUNNABLE, RUNNING, ZOMBIE &#125;;</span><br><span class="line"></span><br><span class="line"><span class="comment">// the information xv6 tracks about each process</span></span><br><span class="line"><span class="comment">// including its register context and state</span></span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">proc</span> &#123;</span></span><br><span class="line">  <span class="keyword">char</span> *mem;                   <span class="comment">// Start of process memory</span></span><br><span class="line">  uint sz;                     <span class="comment">// Size of process memory</span></span><br><span class="line">  <span class="keyword">char</span> *kstack;                <span class="comment">// Bottom of kernel stack</span></span><br><span class="line">                               <span class="comment">// for this process</span></span><br><span class="line">  <span class="keyword">enum</span> proc_state state;       <span class="comment">// Process state</span></span><br><span class="line">  <span class="keyword">int</span> pid;                     <span class="comment">// Process ID</span></span><br><span class="line">  <span class="class"><span class="keyword">struct</span> <span class="title">proc</span> *<span class="title">parent</span>;</span>         <span class="comment">// Parent process</span></span><br><span class="line">  <span class="keyword">void</span> *chan;                  <span class="comment">// If non-zero, sleeping on chan</span></span><br><span class="line">  <span class="keyword">int</span> killed;                  <span class="comment">// If non-zero, have been killed</span></span><br><span class="line">  <span class="class"><span class="keyword">struct</span> <span class="title">file</span> *<span class="title">ofile</span>[<span class="title">NOFILE</span>];</span>  <span class="comment">// Open files</span></span><br><span class="line">  <span class="class"><span class="keyword">struct</span> <span class="title">inode</span> *<span class="title">cwd</span>;</span>           <span class="comment">// Current directory</span></span><br><span class="line">  <span class="class"><span class="keyword">struct</span> <span class="title">context</span> <span class="title">context</span>;</span>      <span class="comment">// Switch here to run process</span></span><br><span class="line">  <span class="class"><span class="keyword">struct</span> <span class="title">trapframe</span> *<span class="title">tf</span>;</span>        <span class="comment">// Trap frame for the</span></span><br><span class="line">                               <span class="comment">// current interrupt</span></span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<p>我们把这段存储进程的个体数据结构叫做 PCB（进程控制块）<br>操作系统为就绪态/阻塞态分别存储了进程列表（process list），用于调度</p>
<h3 id="进程切换"><a href="#进程切换" class="headerlink" title="进程切换"></a>进程切换</h3><p>如果要实现时分复用，首先要支持进程的执行和进程的切换。</p>
<h4 id="上下文切换"><a href="#上下文切换" class="headerlink" title="上下文切换"></a>上下文切换</h4><p>对于停止的进程，寄存器上下文将保存其寄存器的内容。当一个进程停止时，它的寄存器将被保存到这个内存位置。通过恢复这些寄存器（将它们的值放回实际的物理寄存器中），操作系统可以恢复运行该进程。它被称为上下文切换（context switch）。</p>
<p>注意：上下文切换的成本不仅仅来自保存和恢复少量寄存器的操作系统操作。程序运行时，它们在CPU高速缓存、TLB、分支预测器和其他片上硬件中建立了大量的状态。切换到另一个工作会导致此状态被刷新，且与当前运行的作业相关的新状态被引入，这可能导致显著的性能成本。</p>
<h4 id="受限执行"><a href="#受限执行" class="headerlink" title="受限执行"></a>受限执行</h4><p>在最早期操作系统的实现中，对于进程的执行持开放态度，没有任何限制（直接执行协议）</p>
<p><img src="/2021/03/17/操作系统导论-进程篇/D9FF427C-DC64-4ED0-A929-8DB4D609957F.jpg" alt="D9FF427C-DC64-4ED0-A929-8DB4D609957F"></p>
<p>但是这里会遇到两个问题：</p>
<ol>
<li>运行的程序怎么保证不做任何越界的事情，例如访问文件系统时的权限</li>
<li>当运行一个进程时，操作系统怎么让它停下来切换到另一个进程</li>
</ol>
<p>所以如果操作系统不对进程做受限控制，这些问题都无法解决。</p>
<p>首先操作系统结合硬件做了一个权限划分，<strong>用户模式和内核模式</strong>：</p>
<ol>
<li>在用户模式（user mode）下，应用程序不能完全访问硬件资源。</li>
<li>在内核模式（kernel model）下，操作系统可以访问机器的全部资源。</li>
<li>系统新建的进程都处于用户模式下。</li>
</ol>
<p>举个例子，引入了用户模式之后，进程就不能直接发出I/O请求了，这样会导致处理器抛出异常，操作系统终止该进程。</p>
<p>那不对呀？我们平时可以通过open()之类的api来读写文件呀？</p>
<p>其实这是操作系统封装的一组特权操作，叫做<strong>系统调用</strong>，例如访问文件系统、创建进程、分配内存等。并且在进行系统调用时，不是通过提权用户态，而是通过<strong>中断</strong>(trap/interrupt)。</p>
<p>中断将需要执行的指令跳入到内核中，这时内核处于内核态，完成了所有工作之后，操作系统又会调用特殊的指令<strong>中断返回</strong>(return-from-trap)，该指令返回到发起调用的用户程序中，回到用户模式。</p>
<p><img src="/2021/03/17/操作系统导论-进程篇/971D1520-2FAA-458B-B02A-05359281A29C.jpg" alt="971D1520-2FAA-458B-B02A-05359281A29C"></p>
<p>那么问题来了，触发的中断，OS知道运行哪些代码呢？</p>
<p>首先这个不能交由进程来控制，不然就丢失了用户态/内核态的意义。所以OS内核独自维护了一张<strong>中断表</strong>（trap table），记录了不同的中断指令映射的中断处理程序地址，在OS启动时初始化(一开始的trap_init)</p>
<h4 id="中断的分类"><a href="#中断的分类" class="headerlink" title="中断的分类"></a>中断的分类</h4><p>关于中断，还有各种指令和类型。</p>
<img src="/2021/03/17/操作系统导论-进程篇/3EDEB3BC-C8D4-4FD0-A82A-BEED1C87D264.png" alt="3EDEB3BC-C8D4-4FD0-A82A-BEED1C87D264" style="zoom:50%;">

<p>其中时钟中断(timer interrupt)是为了让操作系统重新获得控制权，进而调度其他进程。</p>
<h3 id="进程调度"><a href="#进程调度" class="headerlink" title="进程调度"></a>进程调度</h3><p>进程调度主要就两个问题：性能(performance)和公平(fairness)</p>
<p>性能指时间总和的消耗，公平指各个进程能够公平的得到执行机会。</p>
<p>在讨论进程调度策略之前，我们先做一些假设，然后不断调整假设，找出更优的调度策略：</p>
<p>1．每一个工作运行相同的时间。<br>2．所有的工作同时到达。<br>3．一旦开始，每个工作保持运行直到完成。<br>4．所有的工作只是用CPU（即它们不执行IO操作）。<br>5．每个工作的运行时间是已知的。</p>
<p>并提出第一个性能量化指标：<strong>周转时间</strong>（turnaround time）<br>T(周转时间) = T(完成时间) - T(到达时间)</p>
<p>如果我们假设每个工作同时到达，那么T(达到时间)=0</p>
<h4 id="FIFO"><a href="#FIFO" class="headerlink" title="FIFO"></a>FIFO</h4><p>假设工作到达的顺序为A-&gt;B-&gt;C，并且几乎同时到达，忽略不计，运行时间都是10s的话，T(周转时间) = (10+20+30)/3 = 20</p>
<p><img src="/2021/03/17/操作系统导论-进程篇/739D47E6-4A1E-44D8-9536-E3D149F9211C.png" alt="739D47E6-4A1E-44D8-9536-E3D149F9211C"></p>
<p>如果A运行时间变为100s的话，那么 T(周转时间) = (100+110+120)/3 = 110</p>
<p><img src="/2021/03/17/操作系统导论-进程篇/11E32EB5-6CC6-4F70-A361-9C2C6A304A59.png" alt="11E32EB5-6CC6-4F70-A361-9C2C6A304A59"></p>
<p>可以发现FIFO（先进先出）的最主要问题是一些消耗资源较小的任务会被排在消耗资源更重的任务后面，导致整体的周转时间被拉长。</p>
<h4 id="SJF-amp-amp-STCF"><a href="#SJF-amp-amp-STCF" class="headerlink" title="SJF &amp;&amp; STCF"></a>SJF &amp;&amp; STCF</h4><p>那基于这个问题，我们可以很直观的想到一个解决方法：贪心的让工作越短的任务越先执行，也就是SJF（最短作业优先）</p>
<p><img src="/2021/03/17/操作系统导论-进程篇/09E5948F-7E98-4896-B426-CB1DDDDABB14.png" alt="09E5948F-7E98-4896-B426-CB1DDDDABB14"></p>
<p>如果所有工作都同时达到，那SJF确实是最优的算法，那我们把假设2改为实际情况下的所有的工作随机到达呢？</p>
<p>如果B，C在A执行到t=10的时候到达，那么T(周转时间) = (100+100+110) / 3 ~= 103.33s<br>面临了类似FIFO的问题</p>
<p><img src="/2021/03/17/操作系统导论-进程篇/F70CB601-035D-4DA4-83ED-C7817ED1241C.png" alt="F70CB601-035D-4DA4-83ED-C7817ED1241C"></p>
<p>为了解决这个问题，我们需要把假设3改为实际情况，操作系统拥有时钟中断和上下文切换的机制，工作将会以抢占式的方式进行。</p>
<p>那我们基于 SJF 引入抢占的概念之后，被称为STCF（抢占式最短作业优先），规则变为谁的完成时间最短，就先执行谁的。</p>
<p><img src="/2021/03/17/操作系统导论-进程篇/CF57A32E-5637-4BCC-B3B1-EDFE74F41464.png" alt="CF57A32E-5637-4BCC-B3B1-EDFE74F41464"></p>
<p>当应用了以上策略之后，T(周转时间) = (120+10+20)/3 = 50s</p>
<p>如果我们知道任务长度，而且任务只使用CPU，而我们唯一的衡量是周转时间，STCF将是一个很好的策略。事实上，对于许多早期批处理系统，这些类型的调度算法有一定的意义。然而，引入分时系统改变了这一切。现在，用户将会坐在终端前面，同时也要求系统的交互性好。因此，一个新的度量标准诞生了：<strong>响应时间</strong>（response time）。</p>
<p>T(响应时间) = T(首次运行)-T(到达时间)</p>
<p>相应时间更像是一个公平性指标，STCF在这方面的表现预期会很不好，假设在终端有一个输入，STCF会优先运行完其他耗时更短的工作，这时候给我们的交互就会是坐在屏幕前傻等~</p>
<h4 id="RR"><a href="#RR" class="headerlink" title="RR"></a>RR</h4><p>轮转算法RR(Round-Robin)，RR会在每一个时间片内运行一个任务，下一个时间片选择队列中的下一个任务，反复执行直到所有任务完成。</p>
<p>假设现在有三个任务 A B C，都会运行5s，在STCF策略下，<br>T(平均响应时间) = (0+5+10)/3 = 5s</p>
<p><img src="/2021/03/17/操作系统导论-进程篇/08210689-F1C3-47A6-8D20-2F4FD40C93B2.png" alt="08210689-F1C3-47A6-8D20-2F4FD40C93B2"></p>
<p>而在RR策略下，T(平均响应时间) = (0+1+2)/3 = 1s</p>
<p><img src="/2021/03/17/操作系统导论-进程篇/E084EA4F-08FE-40A7-98C3-8B2434988445.png" alt="E084EA4F-08FE-40A7-98C3-8B2434988445"></p>
<p>时间片长度对于RR是至关重要的。越短，RR在响应时间上表现越好。然而，时间片太短是有问题的：突然上下文切换的成本将影响整体性能。因此，系统设计者需要权衡时间片的长度，使其足够长，以便摊销（amortize）上下文切换成本，而又不会使系统不及时响应。</p>
<h4 id="STCF-VS-RR"><a href="#STCF-VS-RR" class="headerlink" title="STCF VS RR"></a>STCF VS RR</h4><p>可以发现，以上的调度策略中（SJF、STCF）优化周转时间，但对响应时间不利。第二种类型（RR）优化响应时间，但对周转时间不利。</p>
<p>就好像<strong>性能</strong>和<strong>公平</strong>是鱼与熊掌，不可兼得，接下来会介绍操作系统是如何权衡这两个指标的。</p>
<h4 id="引入IO"><a href="#引入IO" class="headerlink" title="引入IO"></a>引入IO</h4><p>现在还有两个前提条件需要替换：<br>4．所有的工作只是用CPU（即它们不执行IO操作）。<br>5．每个工作的运行时间是已知的。</p>
<p>如果引入IO之后，策略可以做一个通用处理，即在IO等待时，分片执行其他任务。</p>
<p><img src="/2021/03/17/操作系统导论-进程篇/E1D5FAC7-B358-478D-AC0B-DB4442B9EDBE.png" alt="E1D5FAC7-B358-478D-AC0B-DB4442B9EDBE"></p>
<h4 id="MLFQ"><a href="#MLFQ" class="headerlink" title="MLFQ"></a>MLFQ</h4><p>以上调度最大的问题还是工作运行时间是未知的。</p>
<p>多级反馈队列(Multi-level FeedbackQueue，MLFQ)作为获得图灵奖的调度算法，至今还使用在现代操作系统中。</p>
<p>它主要需要解决以下几个问题：</p>
<ol>
<li>优化周转时间</li>
<li>降低响应时间</li>
<li>从历史中获取进程的特征，调整调度策略</li>
</ol>
<p>写给出最终的规则：<br>● 规则1：如果A的优先级 &gt; B的优先级，运行A（不运行B）。<br>● 规则2：如果A的优先级 = B的优先级，轮转运行A和B。<br>● 规则3：工作进入系统时，放在最高优先级（最上层队列）。<br>● 规则4：一旦工作用完了其在某一层中的时间配额（无论中间主动放弃了多少次CPU），就降低其优先级（移入低一级队列）。<br>● 规则5：经过一段时间S，就将系统中所有工作重新加入最高优先级队列。</p>
<p>MLFQ由很多独立的队列组成，每个队列有不同的优先级，优先执行高优先级队列中的任务，同优先级队列的任务轮转运行。</p>
<p>所以MLFQ中的本质问题是 <strong>如何设置任务的优先级</strong></p>
<img src="/2021/03/17/操作系统导论-进程篇/51EB5FB1-1E66-4B81-9FAE-A26B3219E8CD.png" alt="51EB5FB1-1E66-4B81-9FAE-A26B3219E8CD" style="zoom:80%;">

<p>工作负载主要这两种类型：</p>
<ol>
<li>运行时间短，频繁放弃CPU的交互性工作</li>
<li>运行时间长，CPU密集型的工作</li>
</ol>
<p>工作刚进入OS时，我们假设它是个短任务，赋予其最高优先级，因为之前我们知道，短任务优先执行能够提高周转时间（规则3）</p>
<p>如果是长任务，慢慢的就会被移入更低优先级的队列（规则4）</p>
<p>但是存在一个问题，如果系统有太多交互性的短作业，长作业会有饥饿问题，所以OS决定周期性的提升所有任务的优先级，让其有机会得到执行（规则5）</p>
<p>总结：MLFQ 对于短时间运行的交互型工作，获得类似于SJF/STCF的很好的全局性能，同时对长时间运行的CPU密集型负载也可以公平地、不断地稳步向前。</p>
<h4 id="多核进程调度问题"><a href="#多核进程调度问题" class="headerlink" title="多核进程调度问题"></a>多核进程调度问题</h4><p>之前我们讨论的调度策略都是在单核心上的，但随着硬件的发展，CPU的性能也逐渐进入瓶颈，所以现在的架构多为多核CPU架构。</p>
<p>多核虽然能够带来更多的CPU资源，但也会带来一些问题。</p>
<p><strong>CPU缓存一致性问题</strong></p>
<p>由于时间局部性，CPU缓存会非常有用，但多个CPU在中断时机不巧时会遇到缓存一致性问题。</p>
<p><img src="/2021/03/17/操作系统导论-进程篇/9A51328E-8F57-43BA-8630-C1F01C642517.png" alt="9A51328E-8F57-43BA-8630-C1F01C642517"></p>
<p><strong>缓存亲和</strong></p>
<p>之前我们了解到，一个进程在某个CPU上执行时，会在该CPU的缓存上维护很多状态。所以尽量避免把在CPU上执行的进程切换到另一个CPU上执行，因为需要重新加载各种缓存结构。</p>
<p><strong>单队列调度</strong></p>
<p>回到多核进程调度上来，在MLFQ的基础上主要有两种方式，单队列调度和多队列调度。</p>
<p>单队列调度，即将所有的进程放到一个MLFQ中维护，但由于需要在多个CPU上做进程调度，在访问队列的下一个进程等操作的时候，需要加锁，且不利于扩展。</p>
<p><img src="/2021/03/17/操作系统导论-进程篇/F757B999-B144-4A7D-9366-E6CF8E09CECC.png" alt="F757B999-B144-4A7D-9366-E6CF8E09CECC"></p>
<p>单队列调度的方式的CPU执行时间序列如下：</p>
<p><img src="/2021/03/17/操作系统导论-进程篇/D183F4D3-8393-49F3-85AC-ACA099EB5A9C.png" alt="D183F4D3-8393-49F3-85AC-ACA099EB5A9C"></p>
<p>可以发现这种方式对于CPU缓存不亲和，虽然会基于该策略做一些优化，但实际效果并不是很好</p>
<p><strong>多队列调度</strong></p>
<p>多队列调度的方式更具备扩展性，队列的数量随着CPU数量而增加，不会因为CPU数据增多引起锁的争用更加剧烈。</p>
<p>并且对于缓存更加亲和。</p>
<p><img src="/2021/03/17/操作系统导论-进程篇/E442FEA5-57A6-4661-86CC-56CC93FD1643.png" alt="E442FEA5-57A6-4661-86CC-56CC93FD1643"></p>
<p><img src="/2021/03/17/操作系统导论-进程篇/4B39B5A0-65BB-471C-AC26-E766EB60D230.png" alt="4B39B5A0-65BB-471C-AC26-E766EB60D230"></p>
<p>但这种方式同时也存在一个问题：一核有难，八核围观。调度队列的分配不均让CPU资源无法得到充分利用。</p>
<p>直观的解决方式是迁移(migrate)，工作量较少的队列会看看其他队列的工作负载，如果少的话就会迁移一些任务到自己队列中处理。</p>
<p><img src="/2021/03/17/操作系统导论-进程篇/729EDA6F-CFDC-4EAD-9F05-C49A74EB05CA.png" alt="729EDA6F-CFDC-4EAD-9F05-C49A74EB05CA"></p>
<p><img src="/2021/03/17/操作系统导论-进程篇/1F679B26-15C8-4760-9AB1-259AB2BEEAAE.png" alt="1F679B26-15C8-4760-9AB1-259AB2BEEAAE"></p>
<p>总结：其中单队列的方式（SQMS）比较容易构建，负载均衡较好，但在扩展性和缓存亲和度方面有着固有的缺陷。多队列的方式（MQMS）有很好的扩展性和缓存亲和度，但实现负载均衡却很困难，也更复杂</p>
<h2 id="参考"><a href="#参考" class="headerlink" title="参考"></a>参考</h2><p>《操作系统导论》 <a href="https://book.douban.com/subject/33463930/" target="_blank" rel="noopener">https://book.douban.com/subject/33463930/</a></p>
<p>微信公众号-低并发编程</p>

      
    </div>
    
    
    

    

    
      <div>
        <div style="padding: 10px 0; margin: 20px auto; width: 90%; text-align: center;">
  <div>觉得好的话就打赏Ta一瓶冰阔落吧</div>
  <button id="rewardButton" disable="enable" onclick="var qr = document.getElementById('QR'); if (qr.style.display === 'none') {qr.style.display='block';} else {qr.style.display='none'}">
    <span>打赏</span>
  </button>
  <div id="QR" style="display: none;">

    
      <div id="wechat" style="display: inline-block">
        <img id="wechat_qr" src="/images/wechatpay.jpg" alt="Yu 微信支付">
        <p>微信支付</p>
      </div>
    

    
      <div id="alipay" style="display: inline-block">
        <img id="alipay_qr" src="/images/alipay.jpg" alt="Yu 支付宝">
        <p>支付宝</p>
      </div>
    

    

  </div>
</div>

      </div>
    

    
      <div>
        <ul class="post-copyright">
  <li class="post-copyright-author">
    <strong>本文作者：</strong>
    Yu
  </li>
  <li class="post-copyright-link">
    <strong>本文链接：</strong>
    <a href="https://yujunjiex.gitee.io/2021/03/17/操作系统导论-进程篇/" title="操作系统导论(进程篇)">https://yujunjiex.gitee.io/2021/03/17/操作系统导论-进程篇/</a>
  </li>
  <li class="post-copyright-license">
    <strong>版权声明： </strong>
    本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/3.0/" rel="external nofollow" target="_blank">CC BY-NC-SA 3.0</a> 许可协议。转载请注明出处！
  </li>
</ul>

      </div>
    

    <footer class="post-footer">
      
        <div class="post-tags">
          
            <a href="/tags/操作系统/" rel="tag"># 操作系统</a>
          
            <a href="/tags/linux/" rel="tag"># linux</a>
          
            <a href="/tags/进程调度/" rel="tag"># 进程调度</a>
          
        </div>
      

      
      
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/2020/03/25/春招有感/" rel="next" title="春招有感">
                <i class="fa fa-chevron-left"></i> 春招有感
              </a>
            
          </div>

          <span class="post-nav-divider"></span>

          <div class="post-nav-prev post-nav-item">
            
              <a href="/2021/07/19/记录一次小程序抢名额的逆向过程/" rel="prev" title="记录一次小程序抢名额的逆向过程">
                记录一次小程序抢名额的逆向过程 <i class="fa fa-chevron-right"></i>
              </a>
            
          </div>
        </div>
      

      
      
    </footer>
  </div>
  
  
  
  </article>



    <div class="post-spread">
      
        <!-- Go to www.addthis.com/dashboard to customize your tools -->
<div class="addthis_inline_share_toolbox">
  <script type="text/javascript" src="//s7.addthis.com/js/300/addthis_widget.js#pubid=ra-5b03d4a278f58ab9" async="async"></script>
</div>

      
    </div>
  </div>


          </div>
          


          

  
    <div class="comments" id="comments">
    </div>
  



        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap">
            文章目录
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview-wrap">
            站点概览
          </li>
        </ul>
      

      <section class="site-overview-wrap sidebar-panel">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope="" itemtype="http://schema.org/Person">
            
              <img class="site-author-image" itemprop="image" src="/images/xiaomai.png" alt="Yu">
            
              <p class="site-author-name" itemprop="name">Yu</p>
              <p class="site-description motion-element" itemprop="description"></p>
          </div>

          <nav class="site-state motion-element">

            
              <div class="site-state-item site-state-posts">
              
                <a href="/archives/">
              
                  <span class="site-state-item-count">28</span>
                  <span class="site-state-item-name">日志</span>
                </a>
              </div>
            

            

            
              
              
              <div class="site-state-item site-state-tags">
                <a href="/tags/index.html">
                  <span class="site-state-item-count">30</span>
                  <span class="site-state-item-name">标签</span>
                </a>
              </div>
            

          </nav>

          

          
            <div class="links-of-author motion-element">
                
                  <span class="links-of-author-item">
                    <a href="https://github.com/yujunjiex" target="_blank" title="GitHub">
                      
                        <i class="fa fa-fw fa-github"></i>GitHub</a>
                  </span>
                
            </div>
          

          
          

          
          

          

        </div>
      </section>

      
      <!--noindex-->
        <section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">

            
              
            

            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#操作系统导论（进程篇）"><span class="nav-number">1.</span> <span class="nav-text">操作系统导论（进程篇）</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#前言"><span class="nav-number">1.1.</span> <span class="nav-text">前言</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#入口"><span class="nav-number">1.2.</span> <span class="nav-text">入口</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#CPU虚拟化"><span class="nav-number">1.3.</span> <span class="nav-text">CPU虚拟化</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#进程"><span class="nav-number">1.4.</span> <span class="nav-text">进程</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#进程API"><span class="nav-number">1.4.1.</span> <span class="nav-text">进程API</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#系统调用"><span class="nav-number">1.4.1.1.</span> <span class="nav-text">系统调用</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#进程状态机"><span class="nav-number">1.4.2.</span> <span class="nav-text">进程状态机</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#进程数据结构"><span class="nav-number">1.4.3.</span> <span class="nav-text">进程数据结构</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#进程切换"><span class="nav-number">1.4.4.</span> <span class="nav-text">进程切换</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#上下文切换"><span class="nav-number">1.4.4.1.</span> <span class="nav-text">上下文切换</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#受限执行"><span class="nav-number">1.4.4.2.</span> <span class="nav-text">受限执行</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#中断的分类"><span class="nav-number">1.4.4.3.</span> <span class="nav-text">中断的分类</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#进程调度"><span class="nav-number">1.4.5.</span> <span class="nav-text">进程调度</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#FIFO"><span class="nav-number">1.4.5.1.</span> <span class="nav-text">FIFO</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#SJF-amp-amp-STCF"><span class="nav-number">1.4.5.2.</span> <span class="nav-text">SJF &amp;&amp; STCF</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#RR"><span class="nav-number">1.4.5.3.</span> <span class="nav-text">RR</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#STCF-VS-RR"><span class="nav-number">1.4.5.4.</span> <span class="nav-text">STCF VS RR</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#引入IO"><span class="nav-number">1.4.5.5.</span> <span class="nav-text">引入IO</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#MLFQ"><span class="nav-number">1.4.5.6.</span> <span class="nav-text">MLFQ</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#多核进程调度问题"><span class="nav-number">1.4.5.7.</span> <span class="nav-text">多核进程调度问题</span></a></li></ol></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#参考"><span class="nav-number">1.5.</span> <span class="nav-text">参考</span></a></li></ol></li></ol></div>
            

          </div>
        </section>
      <!--/noindex-->
      

      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; 2018 &mdash; <span itemprop="copyrightYear">2023</span>
  <span class="with-love">
    <i class="fa fa-heartbeat"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">Yu</span>

  
    <span class="post-meta-divider">|</span>
    <span class="post-meta-item-icon">
      <i class="fa fa-area-chart"></i>
    </span>
    
      <span class="post-meta-item-text">Site words total count&#58;</span>
    
    <span title="Site words total count">46.7k</span>
  
</div>


  <div class="powered-by">由 <a class="theme-link" target="_blank" href="https://hexo.io">Hexo</a> 强力驱动</div>



  <span class="post-meta-divider">|</span>



  <div class="theme-info">主题 &mdash; <a class="theme-link" target="_blank" href="https://github.com/iissnan/hexo-theme-next">NexT.Gemini</a></div>



        







        
      </div>
    </footer>

    
      <div class="back-to-top">
        <i class="fa fa-arrow-up"></i>
        
      </div>
    

    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  












  
  
    <script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script>
  

  
  
    <script type="text/javascript" src="/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>
  

  
  
    <script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>
  


  


  <script type="text/javascript" src="/js/src/utils.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=5.1.4"></script>



  
  


  <script type="text/javascript" src="/js/src/affix.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/schemes/pisces.js?v=5.1.4"></script>



  
  <script type="text/javascript" src="/js/src/scrollspy.js?v=5.1.4"></script>
<script type="text/javascript" src="/js/src/post-details.js?v=5.1.4"></script>

<script type="text/javascript" src="/custom/fold_action.js?v="></script>





  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=5.1.4"></script>



  


  




	





  





  










  <script src="//code.bdstatic.com/npm/leancloud-storage@4.12.0/dist/av-min.js"></script>
  <script src="//unpkg.com/valine/dist/Valine.min.js"></script>
  
  <script type="text/javascript">
    var GUEST = ['nick','mail','link'];
    var guest = 'nick';
    guest = guest.split(',').filter(item=>{
      return GUEST.indexOf(item)>-1;
    });
    new Valine({
        el: '#comments' ,
        verify: false,
        notify: false,
        appId: 'rg0EMRYKYKMhOh1zwqEKS5jz-gzGzoHsz',
        appKey: 'T04zQc0OzQd1uxOqcVomoGqj',
        placeholder: '(= =)~*只有10086嘘寒问暖',
        avatar:'mm',
        guest_info:guest,
        pageSize:'5' || 10,
    });
  </script>



  

  <script type="text/javascript">
    // Popup Window;
    var isfetched = false;
    var isXml = true;
    // Search DB path;
    var search_path = "";
    if (search_path.length === 0) {
      search_path = "search.xml";
    } else if (/json$/i.test(search_path)) {
      isXml = false;
    }
    var path = "/" + search_path;
    // monitor main search box;

    var onPopupClose = function (e) {
      $('.popup').hide();
      $('#local-search-input').val('');
      $('.search-result-list').remove();
      $('#no-result').remove();
      $(".local-search-pop-overlay").remove();
      $('body').css('overflow', '');
    }

    function proceedsearch() {
      $("body")
        .append('<div class="search-popup-overlay local-search-pop-overlay"></div>')
        .css('overflow', 'hidden');
      $('.search-popup-overlay').click(onPopupClose);
      $('.popup').toggle();
      var $localSearchInput = $('#local-search-input');
      $localSearchInput.attr("autocapitalize", "none");
      $localSearchInput.attr("autocorrect", "off");
      $localSearchInput.focus();
    }

    // search function;
    var searchFunc = function(path, search_id, content_id) {
      'use strict';

      // start loading animation
      $("body")
        .append('<div class="search-popup-overlay local-search-pop-overlay">' +
          '<div id="search-loading-icon">' +
          '<i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>' +
          '</div>' +
          '</div>')
        .css('overflow', 'hidden');
      $("#search-loading-icon").css('margin', '20% auto 0 auto').css('text-align', 'center');

      $.ajax({
        url: path,
        dataType: isXml ? "xml" : "json",
        async: true,
        success: function(res) {
          // get the contents from search data
          isfetched = true;
          $('.popup').detach().appendTo('.header-inner');
          var datas = isXml ? $("entry", res).map(function() {
            return {
              title: $("title", this).text(),
              content: $("content",this).text(),
              url: $("url" , this).text()
            };
          }).get() : res;
          var input = document.getElementById(search_id);
          var resultContent = document.getElementById(content_id);
          var inputEventFunction = function() {
            var searchText = input.value.trim().toLowerCase();
            var keywords = searchText.split(/[\s\-]+/);
            if (keywords.length > 1) {
              keywords.push(searchText);
            }
            var resultItems = [];
            if (searchText.length > 0) {
              // perform local searching
              datas.forEach(function(data) {
                var isMatch = false;
                var hitCount = 0;
                var searchTextCount = 0;
                var title = data.title.trim();
                var titleInLowerCase = title.toLowerCase();
                var content = data.content.trim().replace(/<[^>]+>/g,"");
                var contentInLowerCase = content.toLowerCase();
                var articleUrl = decodeURIComponent(data.url);
                var indexOfTitle = [];
                var indexOfContent = [];
                // only match articles with not empty titles
                if(title != '') {
                  keywords.forEach(function(keyword) {
                    function getIndexByWord(word, text, caseSensitive) {
                      var wordLen = word.length;
                      if (wordLen === 0) {
                        return [];
                      }
                      var startPosition = 0, position = [], index = [];
                      if (!caseSensitive) {
                        text = text.toLowerCase();
                        word = word.toLowerCase();
                      }
                      while ((position = text.indexOf(word, startPosition)) > -1) {
                        index.push({position: position, word: word});
                        startPosition = position + wordLen;
                      }
                      return index;
                    }

                    indexOfTitle = indexOfTitle.concat(getIndexByWord(keyword, titleInLowerCase, false));
                    indexOfContent = indexOfContent.concat(getIndexByWord(keyword, contentInLowerCase, false));
                  });
                  if (indexOfTitle.length > 0 || indexOfContent.length > 0) {
                    isMatch = true;
                    hitCount = indexOfTitle.length + indexOfContent.length;
                  }
                }

                // show search results

                if (isMatch) {
                  // sort index by position of keyword

                  [indexOfTitle, indexOfContent].forEach(function (index) {
                    index.sort(function (itemLeft, itemRight) {
                      if (itemRight.position !== itemLeft.position) {
                        return itemRight.position - itemLeft.position;
                      } else {
                        return itemLeft.word.length - itemRight.word.length;
                      }
                    });
                  });

                  // merge hits into slices

                  function mergeIntoSlice(text, start, end, index) {
                    var item = index[index.length - 1];
                    var position = item.position;
                    var word = item.word;
                    var hits = [];
                    var searchTextCountInSlice = 0;
                    while (position + word.length <= end && index.length != 0) {
                      if (word === searchText) {
                        searchTextCountInSlice++;
                      }
                      hits.push({position: position, length: word.length});
                      var wordEnd = position + word.length;

                      // move to next position of hit

                      index.pop();
                      while (index.length != 0) {
                        item = index[index.length - 1];
                        position = item.position;
                        word = item.word;
                        if (wordEnd > position) {
                          index.pop();
                        } else {
                          break;
                        }
                      }
                    }
                    searchTextCount += searchTextCountInSlice;
                    return {
                      hits: hits,
                      start: start,
                      end: end,
                      searchTextCount: searchTextCountInSlice
                    };
                  }

                  var slicesOfTitle = [];
                  if (indexOfTitle.length != 0) {
                    slicesOfTitle.push(mergeIntoSlice(title, 0, title.length, indexOfTitle));
                  }

                  var slicesOfContent = [];
                  while (indexOfContent.length != 0) {
                    var item = indexOfContent[indexOfContent.length - 1];
                    var position = item.position;
                    var word = item.word;
                    // cut out 100 characters
                    var start = position - 20;
                    var end = position + 80;
                    if(start < 0){
                      start = 0;
                    }
                    if (end < position + word.length) {
                      end = position + word.length;
                    }
                    if(end > content.length){
                      end = content.length;
                    }
                    slicesOfContent.push(mergeIntoSlice(content, start, end, indexOfContent));
                  }

                  // sort slices in content by search text's count and hits' count

                  slicesOfContent.sort(function (sliceLeft, sliceRight) {
                    if (sliceLeft.searchTextCount !== sliceRight.searchTextCount) {
                      return sliceRight.searchTextCount - sliceLeft.searchTextCount;
                    } else if (sliceLeft.hits.length !== sliceRight.hits.length) {
                      return sliceRight.hits.length - sliceLeft.hits.length;
                    } else {
                      return sliceLeft.start - sliceRight.start;
                    }
                  });

                  // select top N slices in content

                  var upperBound = parseInt('1');
                  if (upperBound >= 0) {
                    slicesOfContent = slicesOfContent.slice(0, upperBound);
                  }

                  // highlight title and content

                  function highlightKeyword(text, slice) {
                    var result = '';
                    var prevEnd = slice.start;
                    slice.hits.forEach(function (hit) {
                      result += text.substring(prevEnd, hit.position);
                      var end = hit.position + hit.length;
                      result += '<b class="search-keyword">' + text.substring(hit.position, end) + '</b>';
                      prevEnd = end;
                    });
                    result += text.substring(prevEnd, slice.end);
                    return result;
                  }

                  var resultItem = '';

                  if (slicesOfTitle.length != 0) {
                    resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + highlightKeyword(title, slicesOfTitle[0]) + "</a>";
                  } else {
                    resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + title + "</a>";
                  }

                  slicesOfContent.forEach(function (slice) {
                    resultItem += "<a href='" + articleUrl + "'>" +
                      "<p class=\"search-result\">" + highlightKeyword(content, slice) +
                      "...</p>" + "</a>";
                  });

                  resultItem += "</li>";
                  resultItems.push({
                    item: resultItem,
                    searchTextCount: searchTextCount,
                    hitCount: hitCount,
                    id: resultItems.length
                  });
                }
              })
            };
            if (keywords.length === 1 && keywords[0] === "") {
              resultContent.innerHTML = '<div id="no-result"><i class="fa fa-search fa-5x" /></div>'
            } else if (resultItems.length === 0) {
              resultContent.innerHTML = '<div id="no-result"><i class="fa fa-frown-o fa-5x" /></div>'
            } else {
              resultItems.sort(function (resultLeft, resultRight) {
                if (resultLeft.searchTextCount !== resultRight.searchTextCount) {
                  return resultRight.searchTextCount - resultLeft.searchTextCount;
                } else if (resultLeft.hitCount !== resultRight.hitCount) {
                  return resultRight.hitCount - resultLeft.hitCount;
                } else {
                  return resultRight.id - resultLeft.id;
                }
              });
              var searchResultList = '<ul class=\"search-result-list\">';
              resultItems.forEach(function (result) {
                searchResultList += result.item;
              })
              searchResultList += "</ul>";
              resultContent.innerHTML = searchResultList;
            }
          }

          if ('auto' === 'auto') {
            input.addEventListener('input', inputEventFunction);
          } else {
            $('.search-icon').click(inputEventFunction);
            input.addEventListener('keypress', function (event) {
              if (event.keyCode === 13) {
                inputEventFunction();
              }
            });
          }

          // remove loading animation
          $(".local-search-pop-overlay").remove();
          $('body').css('overflow', '');

          proceedsearch();
        }
      });
    }

    // handle and trigger popup window;
    $('.popup-trigger').click(function(e) {
      e.stopPropagation();
      if (isfetched === false) {
        searchFunc(path, 'local-search-input', 'local-search-result');
      } else {
        proceedsearch();
      };
    });

    $('.popup-btn-close').click(onPopupClose);
    $('.popup').click(function(e){
      e.stopPropagation();
    });
    $(document).on('keyup', function (event) {
      var shouldDismissSearchPopup = event.which === 27 &&
        $('.search-popup').is(':visible');
      if (shouldDismissSearchPopup) {
        onPopupClose();
      }
    });
  </script>





  


  

  

  
  

  

  

  


</body>
</html>

